package org.zlb.algorithm.tree;

import java.util.ArrayList;
import java.util.List;

/**
 * 哈夫曼树又称最优树
 * 构造算法：
 * 1、根据给定的n个权值{w1, w2, w3 ... wn }，构造n棵只有根节点的二叉树，令起权值为wj
 * 2、在森林中选取两棵根节点权值最小的树作为左右子树，构造一颗新的二叉树，置新二叉树根节点权值为其左右子树根节点权值之和。注意，左子树的权值应小于右子树的权值。
 * 3、从森林中删除这两棵树，同时将新得到的二叉树加入森林中。（换句话说，之前的2棵最小的根节点已经被合并成一个新的结点了）
 * 4、重复上述两步，直到只含一棵树为止，这棵树即是 哈弗曼树。
 * 
 * @author zhoulingbo
 * @date 2021/09/17
 */
public class HuffmanTree {

    private String name; // 名称
    private int weight; // 权重
    private HuffmanTree parent; // 父节点
    private HuffmanTree left; // 左节点
    private HuffmanTree right; // 右节点
    private String code; // 编码格式left-0,right-1

    public HuffmanTree(String name, int weight) {
        this.name = name;
        this.weight = weight;
    }

    public String getName() {
        return name;
    }

    public void setName(String name) {
        this.name = name;
    }

    public int getWeight() {
        return weight;
    }

    public void setWeight(int weight) {
        this.weight = weight;
    }

    public HuffmanTree getParent() {
        return parent;
    }

    public void setParent(HuffmanTree parent) {
        this.parent = parent;
    }

    public HuffmanTree getLeft() {
        return left;
    }

    public void setLeft(HuffmanTree left) {
        this.left = left;
    }

    public HuffmanTree getRight() {
        return right;
    }

    public void setRight(HuffmanTree right) {
        this.right = right;
    }
    
    public String getCode() {
        return code;
    }

    public void setCode(String code) {
        this.code = code;
    }

    /**
     * 获取所以叶子节点
     * @return
     */
    public List<HuffmanTree> leafCodes() {
        List<HuffmanTree> list = new ArrayList<>();
        list.addAll(leafCodes(this, "0"));
        return list;
    }
    
    private List<HuffmanTree> leafCodes(HuffmanTree tree, String parentCode) {
        if (tree == null)
            return new ArrayList<>();
        
        List<HuffmanTree> list = new ArrayList<HuffmanTree>();
        if (tree.getLeft() == null && tree.getRight() == null) {
            tree.setCode(parentCode);
            list.add(tree);
            return list;
        }
        
        if (tree.getLeft() != null) {
            List<HuffmanTree> leftList = leafCodes(tree.getLeft(), parentCode + "0");
            list.addAll(leftList);
        }
        
        if (tree.getRight() != null) {
            List<HuffmanTree> rightList = leafCodes(tree.getRight(), parentCode + "1");
            list.addAll(rightList);
        }
        
        return list;
    }
}
